package com.cat.dataStructure;


/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/description/
 * @create 2025/8/14 15:20
 * @since JDK17
 */

public class Solution09 {
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        int[] rearmax = new int[n];
        rearmax[n - 1] = nums[n - 1];
        // 后缀最大数组
        for (int i = n - 2; i >= 2; i--) {
            rearmax[i] = Math.max(nums[i], rearmax[i + 1]);
        }
        for (int i = 1; i < n - 1; i++) {
            max = Math.max(max, nums[i - 1]);
            ans = Math.max(ans, ((long) max - nums[i]) * rearmax[i + 1]);
        }
        return ans;
    }
}
